﻿package list;

import common.Node;

/**
 * 给定一个单链表的头部节点head，链表长度为N，如果N为偶数，那么前N/2个节点算作作伴去，后N/2个节点算作右半区；如果N为奇数，那么
 * 前N/2个节点算作
 * 
 * @author Administrator
 *
 */
public class 按照左右半区的方式重新组合单链表 {

	public static void rearangeList(Node head) {
		if (head == null || head.next == null) {
			return;
		}
		Node middle = head;
		Node right = head.next;
		while (middle.next != null && right.next.next != null) {
			right = right.next.next;
			middle = middle.next;
		}
		right = middle.next;
		middle.next = null;
		mergeLR(head, right);
	}

	/**
	 * 交换的合并左右两个链表
	 * 
	 * @param left
	 * @param right
	 */
	public static void mergeLR(Node left, Node right) {
		Node next = null;
		while (left.next != null) {
			next = right.next;
			right.next = left.next;
			left.next = right;
			left = right.next;
			right = next;
		}
		left.next = right;
	}
}
